package problems.practice;

import java.util.Stack;

/**
 * 6202. 使用机器人打印字典序最小的字符串
 * <p>https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/</p>
 *
 * @author habitplus
 * @since 2022/10/9 16:26
 */
public class T6202 {
    /**
     * 贪心 + 辅助栈
     */
    public String robotWithString(String s) {
        char[] chs = s.toCharArray();
        int m = 26;
        int[] cntMap = new int[26];
        int minIdx = 0;
        Stack<Character> stack = new Stack<>();
        StringBuilder ret = new StringBuilder();

        for (char c : chs) ++cntMap[c - 'a'];

        for (char c : chs) {
            // 当前字符入栈，同时对应的数量减一
            stack.push(c);
            --cntMap[c - 'a'];

            // 计算后续最小的字符
            while (minIdx < m && cntMap[minIdx] == 0) ++minIdx;

            // 栈顶字符 <= 后续的最小字符，则出栈
            while (!stack.isEmpty() && stack.peek() - 'a' <= minIdx) {
                ret.append(stack.pop());
            }
        }

        return ret.toString();
    }
}
